"""
51. N 皇后
困难
相关标签
premium lock icon
相关企业
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。



示例 1：


输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[["Q"]]


提示：

1 <= n <= 9
"""
from typing import List

res = []
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """

        :param n:
        :return:
        """
        def dfs(last:List,x:int,n:int,dp:List) -> int:
            #通过上一个转为当前,二进制，0 下 1下，2左下，4右下 8左下右
            cur = [0] * n
            for i,num in enumerate(last):
                if num==0:
                    continue
                if num&8==8:
                    cur[i] |= 1
                    if i>0:
                        cur[i-1] |= 2
                    if i+1<n:
                        cur[i+1] |= 4
                    continue

                if num&1==1:
                    cur[i] |= 1
                if num&2==2 and i>0:
                    cur[i-1] |=2
                if num&4==4 and i+1<n:
                    cur[i+1] |=4

            #最后
            if x==n-1:
                one = []
                for j,num in enumerate(cur):
                    if num==0:
                        dp.append(j)
                        for i in dp:
                            one.append('.' * i + 'Q' + '.' * (n - i - 1))
                        dp.pop()
                        res.append(one)
                return cur.count(0)
            else:
                ans = 0
                for i,num in enumerate(cur):
                    #赋值
                    if num==0:
                        cur[i] = 8
                        dp.append(i)
                        ans += dfs(cur,x+1,n,dp)
                        dp.pop()
                        cur[i] = 0
                return ans
        res = []
        dfs([0] * n, 0, n, [])
        return res




    def solveNQueens_res1(self, n: int) -> List[List[str]]:
        """
        状态压缩
        :param n:
        :return:
        """
        ans = []
        queens = [0] * n  # 皇后放在 (r,queens[r])
        col = [False] * n
        #两个斜线：同一斜线的横纵坐标相加或相减是相同的；同方向的不同斜线，相加或相减是唯一的，也就是说如果两点坐标相加或相减的结果相同，那么他门在同一条对角线
        #对于右下的坐标系，左上-右下的相减唯一，左下-右上的相加是唯一
        diag1 = [False] * (n * 2 - 1) #相加的结果，逆对角线，左下到右上，i-1，j+1，所以相加是个定值
        diag2 = [False] * (n * 2 - 1) #相减的结果，对角线,左上到右下，i,j同时+1所以相减是定值
        def dfs(r: int) -> None:
            if r == n:
                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
                return
            # 在 (r,c) 放皇后
            for c, ok in enumerate(col):
                if not ok and not diag1[r + c] and not diag2[r - c]:  # 判断能否放皇后
                    queens[r] = c  # 直接覆盖，无需恢复现场
                    #由于python能自动处理负数，所以没做处理,最终负数会到最右边
                    col[c] = diag1[r + c] = diag2[r - c] = True  # 皇后占用了 c 列和两条斜线
                    dfs(r + 1)
                    col[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场
        dfs(0)
        return ans

if __name__ == '__main__':
    print(Solution().solveNQueens(4))
    print(Solution().solveNQueens(6))
    # print(Solution().solveNQueens_res1(5))
    print(len(Solution().solveNQueens_res1(4)))
    print(len(Solution().solveNQueens_res1(6)))
    # dp = [0,0,1]
    # print(dp.count(0))